package dynamic;


/**
 * 最长公共子序列
 * @author Linxiaozhi
 *
 */
public class LongestCommon {
	char[] x = { ' ', 'A', 'H', 'P', 'E', 'U', 'L', 'A', 'L', 'G', 'O', 'W' };
	char[] y = { ' ', 'H', 'V', 'E', 'A', 'L', 'Q', 'L', 'P', 'U', 'O' };

	int m = x.length - 1;
	int n = y.length - 1;

	int[][] f = new int[m + 1][n + 1];
	Direction[][] a = new Direction[m + 1][n + 1];

	enum Direction {
		LEFT, UPPER, UPPER_LEFT
	}

	void dynamic() {
		int i = 0, j = 0;
		for (i = 0; i <= m; i++)
			f[i][0] = 0;
		for (j = 0; j <= n; j++)
			f[0][j] = 0;
		for (i = 1; i <= m; i++) {
			for (j = 1; j <= n; j++) {
				//f[i][j]
				if (x[i] == y[j]) {
					f[i][j] = f[i - 1][j - 1] + 1;
					a[i][j] = Direction.UPPER_LEFT;
				} else {
					int temp1 = 0, temp2 = 0;
					temp1 = f[i - 1][j];
					temp2 = f[i][j - 1];
					if (temp1 < temp2) {
						f[i][j] = temp2;
						a[i][j] = Direction.UPPER;
					} else {
						f[i][j] = temp1;
						a[i][j] = Direction.LEFT;
					}
				}
			}
		}
	}

	void output() {
		System.out.println("output:" + f[m][n]);
//		int i = m, j = n;
//		List<Character> lists = new ArrayList<Character>();
//		while (i > 0 && j > 0) {
//			switch (a[i][j]) {
//			case UPPER_LEFT:
//				lists.add(x[i]); //或者lists.add(y[j]);
//				i--;
//				j--;
//				break;
//			case UPPER:
//				j--;
//				break;
//			case LEFT:
//				i--;
//			default:
//				break;
//			}
//		}
//		Collections.reverse(lists);
//		System.out.println(lists);
		outputA(m, n);
	}

	void outputA(int i, int j) {
		if (i == 0 || j == 0)
			return;
		if (a[i][j] == Direction.UPPER_LEFT) {
			outputA(i - 1, j - 1);
			System.out.print(x[i]+" ");
		} else if (a[i][j] == Direction.UPPER) {
			outputA(i, j - 1);
		} else if (a[i][j] == Direction.LEFT) {
			outputA(i - 1, j);
		}

	}

	public static void main(String[] args) {
		LongestCommon lc = new LongestCommon();
		lc.dynamic();
		lc.output();
	}
}
